//给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 8 
// -10 <= nums[i] <= 10 
// 
//
// 
//
// 注意：本题与主站 47 题相同： https://leetcode-cn.com/problems/permutations-ii/ 
// Related Topics 数组 回溯 
// 👍 4 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
var result [][]int
func permuteUnique(nums []int) [][]int {

    if len(nums) == 0 {
        return result
    }

    sort.Ints(nums)  // 排序 保证有序

    result = make([][]int, 0)

    track := make([]int, 0, len(nums))
    used := make([]bool, len(nums))  // make([]bool, 0, len) 这种声明无法直接 used[i] 访问

    backtrack(nums, track, used)

    return result

}

// tips: len的空间裁可以使用 cap的空间除了append无法直接使用
func backtrack(nums []int, track []int, used []bool) {
    if len(nums) == len(track) {
        tmp := make([]int, len(nums))  // 这里必须如此声明 否则copy执行不了
        copy(tmp, track)
        result = append(result, tmp)
        return
    }

    for i := 0; i < len(nums); i++ {
        // 路径访问过  或者 前路径值和当前一致并且前路径未访问过

        // 排序后有序，  必须保证相同的前后两值 放入有序
        if used[i] || (i >= 1 && nums[i] == nums[i-1] && !used[i-1]) {
            continue
        }

        track = append(track, nums[i])
        used[i] = true

        backtrack(nums, track, used)

        track = track[0 : len(track) - 1]
        used[i] = false
    }
}
//leetcode submit region end(Prohibit modification and deletion)
